Intelligent test case generation based on branch and bound

doi:10.1016/S1005-8885(14)60291-0

Acta Metallurgica Sinica(English letters) ›› 2014, Vol. 21 ›› Issue (2): 91-97.doi: 10.1016/S1005-8885(14)60291-0

• Others • Previous Articles Next Articles

Intelligent test case generation based on branch and bound

1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China 3. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Received:2013-09-26 Revised:2013-12-31 Online:2014-04-30 Published:2014-04-30
Contact: Ying Xing E-mail:lovelyjamie@yeah.net

Abstract

Abstract:

Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound (BB) is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.

Key words:

test case generation, constraint satisfaction problem, branch and bound, state space search

References

1. Shan J H, Wang J, Qi Z C. Survey on path-oriented automatic generation of test case. Acta Electronica Sinica, 2004, 32(1): 109-113 (in Chinese)

2. King J C. Symbolic execution and program testing. Communications of the ACM, 1976, 19(7): 385-394

3. Wang Y W, Gong Y Z, Xiao Q, et al. Variable range analysis on interval computation. Journal of Beijing University of Posts and Telecommunications, 2009, 32(3): 36-41 (in Chinese)

4. Sharma C, Sabharwal S, Sibal R. A survey on software testing techniques using genetic algorithm. International Journal of Computer Science Issues, 2013, 10(1): 381-393

5. Mao C Y, Yu X X, Chen J F. Generating test data for structural testing based on ant colony optimization. Proceedings of the 12th International Conference on Quality Software (QSIC’12), Aug 27-29, 2012, Xi'an, China. Piscataway, NJ, USA: IEEE, 2012: 98-101

6. Tracey N, Clark J, Mander K. Automated program flaw finding using simulated annealing. ACM SIGSOFT Software Engineering Notes, 1998, 23(2): 73-81

7. Eiben A E, Ruttkay Z. Constraint-satisfaction problems. New York, NY, USA: IOP Publishing Ltd , 1997

8. Lisgara E G, Karolidis G I, Androulakis G S. Advancing the backtrack optimization technique to obtain forecasts of potential crisis periods. Applied Mathematics, 2012, 3(10A):1538-1551

9. Szer D, Charpillet F, Zilberstein S. MAA*: a heuristic search algorithm for solving decentralized POMDPs. Proceedings of the 21st Conference on Uncertainty in Arti?cial Intelligence (UAI’05), Jul 26-29, 2005, Edinburgh, UK. Arlington, VA, USA: AUAI, 2005: 576-583

10. Gao L B, Mishra S K, Shi J M. An extension of branch-and-bound algorithm for solving sum-of-nonlinear-ratios problem. Optimization Letters, 2012, 6(2): 221-230

11. Frost D, Dechter R. Look-ahead value ordering for constraint satisfaction problems. Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95): Vol 1, Aug 20-25, 1995, San Francisco, CA, USA: Morgan Kaufmann, 1995: 572-578

12. Chen X G, Van Beek P. Conflict-directed backjumping revisited. Journal of Artificial Intelligence Research, 2001, 14: 53-81

13. Gallagher M J, Narasimhan V L. Adtest: a test data generation suite for ADA software systems. IEEE Transactions on Software Engineering, 1997, 23(8): 473-484

14. Zhao R L, Harman M, Li Z. Empirical study on the efficiency of search based test generation for EFSM models. Proceedings of the 3rd International Conference on Software Testing, Verification, and Validation Workshops (ICSTW’10), Apr 7-9, 2010, Paris, France. Piscataway, NJ, USA: IEEE, 2010: 222-231

15. Wang Y W, Gong Y Z, Xiao Q, et al. A method of variable range analysis based on abstract interpretation and its applications. Acta Electronica Sinica, 2011, 39(2): 293-303 (in Chinese)

16. Gupta N, Mathur A P, Soffa M L. Automated test data generation using an iterative relaxation method. ACM SIGSOFT Software Engineering Notes. 1998, 23(6): 231-244

17. Wang Y W, Gong Y Z, Xiao Q. A Method of test case generation based on necessary interval set. Journal of Computer-aided Design & Computer Graphics, 2013, 25(4): 550-556 (in Chinese)

18. Bouchachia A. An immune genetic algorithm for software test data generation. Proceedings of the 7th International Conference on Hybrid Intelligent Systems (HIS’07), Sep 17-19, 2007, Kaiserslautern, Germany. Washington, DC, USA: IEEE Computer Society, 2007: 84-89

19. Alba E, Chicano F. Observations in using parallel and sequential evolutionary algorithms for automatic software testing. Computers & Operators Research, 2008, 35(10): 3161-3183

20. Ammann P, Offutt J. Introduction to software testing. New York, NY, USA: Cambridge University Press, 2008:132

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd

Intelligent test case generation based on branch and bound

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments